package com.cat.binaryTree;

/**
 *   @description https://leetcode.cn/problems/binary-tree-maximum-path-sum/
 *   @author 曲大人的喵
 *   @create 2025/9/14 20:39
 *   @since JDK17
 */

public class Solution41 {
    int ans = Integer.MIN_VALUE;
    int f(TreeNode root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }
        int l = f(root.left), r = f(root.right);
        ans = Math.max(ans, root.val + Math.max(l, 0) + Math.max(r, 0));
        return root.val + Math.max(0, Math.max(l, r));
    }

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int cur = f(root);
        cur = Math.max(cur, Math.max(maxPathSum(root.left), maxPathSum(root.right)));
        return Math.max(cur, ans);
    }

    int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = dfs(root.left), r = dfs(root.right);
        ans = Math.max(ans, root.val + Math.max(l, 0) + Math.max(r, 0));
        return Math.max(Math.max(l, r) + root.val, 0);  // 可以一个都不要
    }

}
